package algorithm.leetcode.I201to400;

import java.util.Arrays;

/**
 * 快速排序的变体 那就错了
 * 题意要求将非0数字保持原来的顺序
 */

public class Q283 {

    public void moveZeroes(int[] nums) {
        int zeroIndex = 0, index = 0;

        while (index < nums.length) {
            if (nums[zeroIndex] != 0) { zeroIndex++; index++; }
            else if (nums[zeroIndex] == 0 && nums[index] != 0) swap(nums, zeroIndex, index);
            else if (nums[zeroIndex] == 0 && nums[index] == 0) index++;
        }
    }

    // 不使用额外空间 并且 不会数组溢出,交换两个数字
    private static void swap(int[] nums, int a, int b) {
        // a* = a ^ b
        nums[a] ^= nums[b];
        // b* = b ^ a* = b ^ a ^ b = a
        nums[b] ^= nums[a];
        // a** = a* ^ b* = a ^ b ^ a = b
        nums[a] ^= nums[b];
    }

    public static void main(String[] args) {
        int[] ints = {Integer.MAX_VALUE - 1, Integer.MAX_VALUE};
        swap(ints, 0, 1);
        System.out.println(Arrays.toString(ints));
    }

}
